/* 判断无向图是否存在环（并查集）*/
#include <iostream>
using namespace std;

// 判断无向图是否存在环
#define maxsize 50
#define numedges 6

void init(int parent[], int rank[]) 
{
  for (int i = 0; i < maxsize; ++i)
  {
    parent[i] = -1; // 记录各个结点的根结点
    rank[i] = 0; // 记录各个结点的优先级，已确定根结点
  }
}

// 找到x的根结点，默认是其本身
int find_root(int x, int parent[])
{
  int x_root = x;
  while (parent[x_root] != -1)
    x_root = parent[x_root];
  return x_root;
}

// 并查集 -- 查找x、y结点是否有公共根结点
int Union(int x, int y, int parent[], int rank[])
{
  // 找x的根结点
  int x_root = find_root(x, parent);
  
  // 找y的根结点
  int y_root = find_root(y, parent);
  
  // 两者有共同的根结点
  if (x_root == y_root)
    return 1;
  
  // x优先于y
  else if (rank[x_root] > rank[y_root])
    parent[y_root] = x_root; // x的根结点就是y的根结点
  
  // y优先于x
  else if (rank[x_root] < rank[y_root])
    parent[x_root] = y_root; // y的根结点就是x的根结点
  
  // 同等优先
  else
  {
    // 默认后者优先级高
    rank[y_root]++;
    
    // y的根结点就是x的根结点
    parent[x_root] = y_root;
  }
  return 0;
}

int main()
{
  int parent[maxsize];
  int rank[maxsize];
  
  // 初始化
  init(parent, rank);
  
  // 存储边信息
  int edges[numedges][2] = {{0, 1}, {1, 2}, {1, 3}, {3, 4}, {2, 5}, {5, 4}};
  
  // 遍历边
  for (int i = 0; i < numedges; ++i)
  {
    // 读取边的两个结点
    int x = edges[i][0];
    int y = edges[i][1];
    
    // 两个相邻的结点，是否还有公共的根结点
    if (Union(x, y, parent, rank) == 1)
    {
      cout << "有环!" << endl;
      return 1;
    }
  }
  cout << "没有环!" << endl;
  return 0;
}
